|
题目：
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
例如:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
输入: coins = [2], amount = 3
输出: -1
分析：可以使用贪心+回溯的方法。每次取最大的硬币去匹配金额。
import java.util.*;
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if(amount==0){
return 0;
}
dfs(coins,amount,coins.length-1,0);
return ans==Integer.MAX_VALUE?-1:ans;
}
public void dfs(int[] coins, int amount, int i, int count){
//索引值超过数组下限时return
if(i//贪心 每次用最大面值硬币去拟合金额
int temp_amount = amount-c*coins[i];
int temp_count = c+count;
if(temp_amount==0){//金额刚好凑够则跟之前ans比较取最小值
ans = Math.min(ans,temp_count);
break;
}
if(temp_count+1>=ans){
break;
}
dfs(coins,temp_amount,i-1,temp_count);
}
}
|